import random

from khronos.utils.deque import Deque

class PQueue(object):
    """Class implementing a priority queue."""
    def __init__(self, *items, **kw_items):
        self.__priorities = Deque()
        self.__content = {}
        self.__size = 0
        self.__insert = self.__class__.insert_norotate
        self.__rng = random
        for item, prio in items:
            self.insert(item, prio)
        for item, prio in kw_items.iteritems():
            self.insert(item, prio)
            
    def __repr__(self):
        return "<%s(%d elements) at %s>" % (self.__class__.__name__, self.__size, hex(id(self)))
        
    def __str__(self):
        return self.to_str()
        
    def __len__(self):
        return self.__size
        
    def clear(self):
        self.__priorities = Deque()
        self.__content = {}
        self.__size = 0
        
    def copy(self):
        clone = PQueue()
        clone.__priorities = Deque(self.__priorities)
        clone.__content = dict((p, Deque(items)) for p, items in self.__content.iteritems())
        clone.__size = self.__size
        clone.__insert = self.__insert
        clone.__rng = self.__rng
        return clone
        
    def extend(self, pqueue):
        for items, priority in pqueue.iter_lists_descending():
            try:
                target = self.__content[priority]
            except KeyError:
                target = self.__content[priority] = Deque()
                self.__priorities.insert_sorted(priority)
            finally:
                target.extend(items)
                self.__size += len(items)
                
    def no_shuffling(self):
        """Disable "shuffling mode". Inserting elements no longer causes a random rotation of 
        the deque where the element is inserted, it is merely appended (faster)."""
        self.__insert = self.__class__.insert_norotate
        self.__rng = random
        
    def shuffling(self, rng=random):
        """Shuffle once and enter "shuffling mode" (all future inserts are follow by a random 
        rotation of the deque where the element is inserted)."""
        self.__insert = self.__class__.insert_rotate
        self.__rng = rng
        
    def shuffle(self, rng=None):
        """Shuffle once (elements added after this are not randomized)."""
        if rng is None:
            rng = self.__rng
        for items in self.__content.itervalues():
            rng.shuffle(items)
            
    def insert_norotate(self, item, priority):
        try:
            target = self.__content[priority]
        except KeyError:
            target = self.__content[priority] = Deque()
            self.__priorities.insert_sorted(priority)
        finally:
            target.append(item)
            self.__size += 1
            
    def insert_rotate(self, item, priority, rng=None):
        if rng is None:
            rng = self.__rng
        self.insert_norotate(item, priority)
        target = self.__content[priority]
        target.rotate(int(rng.random() * len(target) + 0.5))
        
    def insert(self, item, priority):
        self.__insert(self, item, priority)
        
    def remove(self, item, priority):
        target = self.__content[priority]
        target.remove(item)
        if len(target) == 0:
            del self.__content[priority]
            self.__priorities.remove_sorted(priority)
        self.__size -= 1
        
    def pop(self):
        """Remove and return the highest priority item."""
        max_prio = self.__priorities[-1]
        target = self.__content[max_prio]
        item = target.pop()
        if len(target) == 0:
            del self.__content[max_prio]
            self.__priorities.pop()
        self.__size -= 1
        return item, max_prio
        
    def popleft(self):
        """Remove and return the lowest priority item."""
        min_prio = self.__priorities[0]
        target = self.__content[min_prio]
        item = target.popleft()
        if len(target) == 0:
            del self.__content[min_prio]
            self.__priorities.popleft()
        self.__size -= 1
        return item, min_prio
        
    def consume_ascending(self):
        """Consume the list in ascending priority order."""
        while self.__size > 0:
            yield self.popleft()
            
    def consume_descending(self):
        """Consume the list in descending priority order."""
        while self.__size > 0:
            yield self.pop()
            
    def iter_ascending(self):
        """Iterate the list in ascending priority order without consuming it."""
        for items, priority in self.iter_lists_ascending():
            for item in items:
                yield item, priority
                
    def iter_descending(self):
        """Iterate the list in descending priority order without consuming it."""
        for items, priority in self.iter_lists_descending():
            for item in items:
                yield item, priority
                
    def iter_lists_ascending(self):
        for priority in self.__priorities:
            yield self.__content[priority], priority
            
    def iter_lists_descending(self):
        for priority in reversed(self.__priorities):
            yield self.__content[priority], priority
            
    def to_str(self, item_format=str):
        lines = ["%s(%d items)" % (self.__class__.__name__, self.__size)]
        for prio in self.__priorities:
            lines.append("\tPrio %s" % (prio,))
            for item in self.__content[prio]:
                lines.append("\t\t%s" % (item_format(item),))
        return "\n".join(lines)
        
